# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
root=TreeNode(1)
root.left=TreeNode(2)
# root.right=TreeNode(1)
# root.left.left=TreeNode(6)
# root.left.right=TreeNode(2)
# root.left.right.left=TreeNode(7)
# root.left.right.right=TreeNode(4)
# root.right.left=TreeNode(0)
# root.right.right=TreeNode(8)
p=TreeNode(1)
q=TreeNode(2)
def dfs(root,p,q,res):
    #边界条件，叶子结点处
    if root.left==None and root.right==None:
        if root.val==p.val:
            return 1
        if root.val==q.val:
            return 1
        return 0
    if root.left:
        left=dfs(root.left,p,q,res)
    else:
        left=0
    if root.right:
        right=dfs(root.right,p,q,res)
    else:
        right=0
    # print(root.left.val,root.right.val)
    print(left,right)
    if left==1 and right==1:
        #找到了
        res.append(root)
        return 2
    if left==2 or right==2:
        #这个也表示已经找到了
        return 2
    if root.val==p.val or root.val==q.val:
        #该项为一个项
        if left+right+1==2:
            res.append(root)
            return 2
        else:
            return 1
    return left+right

def dfs1(root,p,q):
    #先序遍历
    #如果结点不存在，或者在一开始就已经有一个找到了，就直接返回
    if not root or root==p or root==q:return root
    left=dfs1(root.left,p,q)
    right=dfs1(root.right,p,q)
    if not left:return right
    if not right:return left
    return root

    pass
def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    res=[]
    return dfs1(root,p,q)



print(lowestCommonAncestor(root,p,q).val)